1. Field of the Invention
The present invention relates to an elliptic curve cryptosystem apparatus, a storage medium storing an elliptic curve cryptosystem program, and an elliptic curve cryptosystem arithmetic method.
2. Description of the Related Art
An elliptic curve cryptosystem is one of the public key cryptosystem, and is used in the processes of encryption, decryption, signature generation, authentication, etc.
Assuming that p indicates a prime number equal to or larger than 2, and m indicates a natural number equal to or larger than 1, the Weierstrass form elliptic curve over the finite field GF(q) with q=p^m elements is a group obtained by adding the point ∞ referred to as a point at infinity to the group of points (x, y) satisfying the following equation:E:y^2+a1×x×y+a3×y=x^3+a2×x^2+a4×x+a6 (^ indicates a power)The point at infinity ∞ can also be represented by 0.
In the equation, a1, a2, a3, a4, a6, x, and y are elements of the GF (q). Especially, when p is a prime number equal to or larger than 5, the Weierstrass form elliptic curve in the GF(p^m) is a group obtained by adding the point referred to as a point at infinity to the group of points (x, y) satisfying the following equation:E:y{circumflex over (0)}2=x^3+a×x+b The point at infinity ∞ can also be represented by 0.
In the equation, a, b, x, and y are elements of the GF (p^m), and satisfy 4×a^3+27×b^2≠0. The point at infinity ∞ is a point which cannot be represented in the (x, y) coordinate system.
Assume that P indicates a point on the Weierstrass form elliptic curve E in the GF (p^m). The inverse −P is defined as follows:
(1) if P=∞ then −P=∞
(2) if P≠∞ then the following equation holds for P=(x, y)−P=(x,−y)
P1 and P2 are assumed to be two points on the Weierstrass form elliptic curve E. Then, the sum of P1 and P2 is defined as P3=P1+P2 as follows:
(1) if P1=∞ then P3=P2
(2) if P2=then P3=P1
(3) if P1=−P2 then P3=∞
(4) if P1≠P2, then the following equation holds for P1=(x1, y1), P2=(x2, y2), P3=(x3, y3),x3=λ^2−x1−x2, y3=λ×(x1−x3)−y1,
where
λ=(y2−y1)/(x2−x1) when P1≠P2, and
λ=(3×x1^2+a)/(2×y1) when P1=P2
Computing P1+P2 when P1≠P2 is referred to as elliptic curve addition ECADD, and computing P1+P2=2×P1 when P1=P2 is referred to as elliptic curve doubling ECDBL.
FIGS. 1 and 2 are explanatory views of the elliptic curve addition and the elliptic curve doubling. The elliptic curve addition is performed to obtain the point P3=P1+P2=(x3, y3) by turning the intersection point of the straight line connecting the point P1=(x1, y1) on the elliptic curve to the point P2=(x2, y2) on the elliptic curve over the x axis as shown in FIG. 1. The values of x3 and y3 can be represented by the following equations:x3={(y1−y2)/(x1−x2)}^2−x1−x2
(^ indicates a power)y3={(y1−y2)/(x1−x2)}(x1−x3)−y1
The elliptic curve doubling is performed to obtain the point P4=2×P1=(x4, y4) by turning the intersection point of the tangent at the point P1=(x1, y1) on the elliptic curve over the x axis as shown in FIG. 2. The values of x4 and y4 can be represented by the following equations:x4={(3×x1^2+a)/(2×y1)}^2−2×x1y4={(3×x1^2+a)/(2×y1)}(x1−x4)−y1
Scalar multiplication refers to computing the point d×P=P+P+ . . . +P (sum taken d times) for the elliptic curve over the finite field, for the point P on the curve, and for the integer (also referred to as a scalar) d. The scalar multiplication is represented by a combination of the elliptic curve addition and the elliptic curve doubling.
The computation time of the elliptic curve addition, the elliptic curve doubling, and the scalar multiplication can be frequently estimated by a sum of the computation times of multiplication, squaring, and inversion in the GF(q). This is because the practical computations of elliptic curve addition, elliptic curve doubling, and scalar multiplication are a combination of addition, subtraction, multiplication, squaring, and inversion in the GF(q), and in many cases, the computation time of multiplication by addition, subtraction, and constant is comparatively shorter than the computation time of other processes, and can be ignored. For example, the above mentioned elliptic curve addition requires two multiplying operations, one squaring operation, and one inversion operation in the GF (p^m). These operations are represented by 2M+1S+1I.
Normally, the computation time of the inversion in the GF(p^m) is much longer than that of the multiplication and squaring. Therefore, in the actual scalar multiplication, projective coordinates are used in representing a point on an elliptic curve. In the projective coordinate system, a point is represented by a combination of three elements in the GF (p^m) such as (X:Y:Z). However, it is assumed that (X:Y:Z) is the same point as (r×X:r×Y:r×Z) for the element r in the GF(p^m) where r≠0. In the projective coordinate system, the Weierstrass form elliptic curve is represented as follows:E:Y^2×Z=X^3+a×X×Z^2+b×Z^3where x=X/Z, and y=Y/Z is substituted. The point at infinity is represented by ∞=(0:1:0). In the projective coordinate system, there are standard algorithms in which the elliptic curve addition can be computed by 12M+2S, and the elliptic curve doubling can be computed by 7M+5S. Additionally, there are improved projective coordinate systems such as Jacobian coordinates, Chudonovsky coordinates, modified Jacobian coordinates, etc.
On the other hand, a group of points (u, v) satisfying the equation:B×v^2=u^3+A×u^2+u for the elements A and B in the GF(p^m), and a group of the points referred to as points at infinity ∞ are referred to as a Montgomery form elliptic curve. In the projective coordinate system, a point is represented as a set (U:V:W) of three elements in the GF(p^m), and a curve is represented by the following equation:B×V^2×W=U^3+A×U^2×W+U×W^2The point at infinity is represented by ∞=(0:1:0). The formulas of elliptic curve addition and elliptic curve doubling as well as the Weierstrass form elliptic curve are well known.
Since the scalar multiplication on an elliptic curve is represented by a combination of arithmetics of the elliptic curve addition (ECADD) and the elliptic curve doubling (ECDBL), the entire computation time is evaluated based on the number of times of the arithmetics performed. The computation of the point d×P processed by the scalar multiplication is performed using the binary expression of d represented by the equation:d=d[n−1]×2^(n−1)+d[n−2]×2^(n−2)+ . . . +d[1]×2+d[0]
FIG. 3 shows the algorithm 1 of the conventional scalar multiplication.
In FIG. 3, P indicates the initial value of the variable Q[0], the elliptic curve doubling is performed on the point Q[0] in step 3, and an arithmetic result is stored in the Q[0]. If d[i]==1, the elliptic curve addition ECADD is performed on the point Q[0] and the point P in step 5, and the arithmetic result is stored in the point Q[0].
The computation time required in the scalar multiplication of the algorithm 1 is (n−1)/2×E CADD+(n−1)×ECDBL on average. The binary method can be replaced with the signed binary method so as to shorten the average computation time into (n−1)/3×ECADD+(n−1)×ECDBL.
To make the elliptic curve cryptosystem be widespread in the current world, it is necessary to save the resources (memory, circuit amount, etc.) required in the processing time and implementation. In the elliptic curve cryptosystem, an arithmetic referred to as scalar multiplication is commonly used, and is more popularly used in the entire encryption and decryption process. Therefore, the performance of the entire encryption and decryption totally depend on the performance of this portion. Since the scalar multiplication process is a major process in the elliptic curve cryptosystem, it is desired that higher performance can be realized by the scalar multiplication.
However, in the arithmetic method of the above mentioned algorithm 1, it is necessary to perform the elliptic curve addition ECADD based on the arithmetic result Q[0] of the elliptic curve doubling ECDBL, and the shortening of the computation time of the scalar multiplication is limited.
Furthermore, since the elliptic curve cryptosystem can guarantee the security using a key length shorter than a conventional cryptosystem, it has become widespread in such low-power devices as smart cards, etc. However, the side channel attacks can be effective on these devices, and an algorithm of the scalar multiplication resistant to the attacks is required.